/**
 * 
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 19, 2013
 * @version 1.0
 * @description 
 * 		The string "PAYPALISHIRING" is written in a zigzag pattern 
 * 		on a given number of rows like this:  
 * 			P   A   H   N
 * 			A P L S I I G
 * 			Y   I   R
 * 
 * 		And then read line by line: "PAHNAPLSIIGYIR"
 * 		Write the code that will take a string and make this conversion 
 * 		given a number of rows:
 * 			string convert(string text, int nRows);
 * 			convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"
 */
public class ZigzagConversion {
	
	public String solution1(String str, int nRows) {
		StringBuilder sb = new StringBuilder();
		if (nRows <= 1) {
			return str;
		}
		int len = str.length();
		
		// first row
		for (int i = 0; i < len; i += 2 * nRows - 2) {
			sb.append(str.charAt(i));
		}
		
		// rows in the middle
		for(int i = 1; i < nRows - 1; i++) {
			for (int j = i; j < len; j += 2 * nRows - 2) {
				sb.append(str.charAt(j));
				int k = j + (nRows - (i + 1)) * 2;
				if (k < len) {
					sb.append(str.charAt(k));
				}
			}
        }  
		
		// last row
		for (int i = nRows - 1; i < len; i += 2 * nRows - 2) {
			sb.append(str.charAt(i));
		}
		
		return sb.toString();
	}
	
	@Test
	public void testSolution() {
		assert solution1("PA", 3).equals("PA");
		assert solution1("PAYPALISHIRING", 3).equals("PAHNAPLSIIGYIR");
		assert solution1("PAYPALISHIRING", 4).equals("PINALSIGYAHRPI");
	}
}
